Perfect Squares-Greedy
code:solution.cpp
class Solution {
public:
vector<int> sq = {};
int numSquares(int n) {
for (int i=1; pow(i, 2)<=n; i++) sq.push_back(pow(i, 2));
int cnt = 1;
for (; cnt <=n; cnt++) if (isDevided(n, cnt)) return cnt;
return n;
}
bool isDevided(int n, int cnt) {
if (cnt == 1) return find(sq, n);
// 貪欲に、可能性のあるsqを順に当てはめていき再帰的に走査
for (int s : sq) if (isDevided(n-s, cnt-1)) return true;
return false;
}
bool find(vector<int> vec, int val) {
for (int i : vec) if (i == val) return true;
return false;
}
};